﻿//力扣：129. 求根节点到叶节点数字之和
//https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/


//方法：（dfs - 前序遍历）：
//前序遍历按照根节点、左⼦树、右⼦树的顺序遍历⼆叉树的所有节点，通常⽤于⼦节点的状态依赖于⽗节点状态的题⽬。

//算法原理：
//在前序遍历的过程中，我们可以往左右⼦树传递信息，并且在回溯时得到左右⼦树的返回值。递归函数可以帮我们完成两件事：
//1. 将⽗节点的数字与当前节点的信息整合到⼀起，计算出当前节点的数字，然后传递到下⼀层进⾏递归；
//2. 当遇到叶⼦节点的时候，就不再向下传递信息，⽽是将整合的结果向上⼀直回溯到根节点。
//在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和。

//算法流程：
//递归函数设计：int dfs(TreeNode * root, int num)
//1. 返回值：当前⼦树计算的结果（数字和）；
//2. 参数 num：递归过程中往下传递的信息（⽗节点的数字）；
//3. 函数作⽤：整合⽗节点的信息与当前节点的信息计算当前节点数字，并向下传递，在回溯时返回当前⼦树（当前节点作为⼦树根节点）数字和。

//递归函数流程：
//1. 当遇到空节点的时候，说明这条路从根节点开始没有分⽀，返回 0；
//2. 结合⽗节点传下的信息以及当前节点的 val，计算出当前节点数字 sum；
//3. 如果当前结点是叶⼦节点，直接返回整合后的结果 sum；
//4. 如果当前结点不是叶⼦节点，将 sum 传到左右⼦树中去，得到左右⼦树中节点路径的数字和，然后相加后返回结果。
class Solution {
public:
    int sumNumbers(TreeNode* root) 
    {
        return dfs(root, 0);                                // 调用递归函数从根节点开始，初始路径和为 0
    }

    // 辅助递归函数，计算从当前节点到叶节点的数字和
    int dfs(TreeNode* root, int prevSum)
    {
        if (root == nullptr)
        {
            return 0;                                       // 空节点返回 0，表示该路径无效
        }
        
        prevSum = prevSum * 10 + root->val;                 // 计算当前节点路径上的数字

        
        if (root->left == nullptr && root->right == nullptr)// 如果当前节点是叶子节点，直接返回路径数字
        {
            return prevSum;                                 // 此路径的最终数字
        }

        // 递归计算左子树和右子树的路径数字和
        int sum = 0;                                        // 存储当前子树的路径和
        if (root->left)
        {
            sum += dfs(root->left, prevSum);                // 递归左子树
        }
        if (root->right)
        {
            sum += dfs(root->right, prevSum);               // 递归右子树
        }

        return sum;                                         // 返回当前子树的路径和
    }
};